// @algorithm @lc id=611 lang=cpp 
// @title valid-triangle-number


// #define print(...)
// @test([2,2,3,4])=3
// @test([4,2,3,4])=4
// @test([1,1,3,4])=0
// @test([7,0,0,0])=0
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        if(nums.size()<3) return 0;
        sort(nums.begin(), nums.end());
        print("nums=", nums, "\n")
        int ans = 0;
        for(auto a=nums.begin(); a!=nums.end()-2; a++){
            for(auto b=a+1,c=b; b!=nums.end()-1;b++)
            {
                while(c+1!=nums.end() && *(c+1)<*a+*b)
                    c++;
                ans += max(int(c - b), 0);
                print("a=", *a, ", b=", *b, ", c-b=", c-b, ", ans=", ans, "\n")
            }
        }
        return ans;
    }
};